package dp;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Liaorun
 */
public class Coffee {

    public static int minTime1(int[] arr, int n, int a, int b) {
        int[] times = new int[arr.length];
        int[] drink = new int[n];

        return forceMake(arr, times, 0, drink, n, a, b);
    }

    /**
     * 每个人暴力尝试用每一个咖啡机给自己做咖啡
     *
     * @param arr
     * @param times
     * @param kth
     * @param drink
     * @param n
     * @param a
     * @param b
     * @return
     */
    private static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
        if (kth == n) {
            int[] drinkSorted = Arrays.copyOf(drink, kth);
            Arrays.sort(drinkSorted);

            return forceWash(drinkSorted, a, b, 0, 0, 0);
        }

        int time = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            int work = arr[i];
            int pre = times[i];
            drink[kth] = pre + work;
            times[i] = pre + work;
            time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));

            drink[kth] = 0;
            times[i] = pre;
        }
        return time;
    }

    /**
     * 暴力尝试洗咖啡杯的方式，获取花费最短的方式所需要的时间
     *
     * @param drinks
     * @param a
     * @param b
     * @param index
     * @param washLine
     * @param time
     * @return
     */
    private static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
        if (index == drinks.length) {
            return time;
        }
        // 选择1：当前index号咖啡杯，选择用咖啡机刷干净
        int wash = Math.max(drinks[index], washLine) + a;
        // 递归获取后面的咖啡杯清洗情况
        int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));

        // 选择二： 当前index号咖啡杯，选择自然挥发
        int dry = drinks[index] + b;
        int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));

        return Math.min(ans1, ans2);
    }

    public static class Machine {
        public int timePoint;
        public int workTime;

        public Machine(int timePoint, int workTime) {
            this.timePoint = timePoint;
            this.workTime = workTime;
        }
    }

    public static class MachineComparator implements Comparator<Machine> {
        @Override
        public int compare(Machine o1, Machine o2) {
            return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
        }
    }

    /**
     * 每个人暴力尝试用每个咖啡机给自己做咖啡，优化成贪心
     * 暴力尝试：一个一个尝试，走每一条路
     * 贪心: 每次选出一个自己认为最好的路
     *
     * @param arr
     * @param n
     * @param a
     * @param b
     * @return
     */
    public static int minTime2(int[] arr, int n, int a, int b) {

        PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());

        for (int i = 0; i < arr.length; i++) {
            heap.add(new Machine(0, arr[i]));
        }

        int[] drinks = new int[n];
        // 给每人分配一个咖啡机做咖啡
        for (int i = 0; i < n; i++) {
            // 弹出一个最早空闲咖啡机
            Machine cur = heap.poll();
            //
            cur.timePoint += cur.workTime;
            drinks[i] = cur.timePoint;
            heap.add(cur);
        }

        return process(drinks, a, b, 0, 0);
    }

    /**
     * @param drinks   所有人喝完咖啡的时间数组
     * @param a        用咖啡机洗一个咖啡杯的时间
     * @param b        咖啡杯自然干净的时间
     * @param index    当前洗的杯子的下标
     * @param washLine 咖啡机什么时候空闲
     * @return 处理drinks[index..N-1] 这些杯子需要的最短时间
     */
    private static int process(int[] drinks, int a, int b, int index, int washLine) {

        // base case:只有一个咖啡杯的情况
        if (index == drinks.length - 1) {
            // Math.min(开始使用咖啡机洗咖啡杯的时间+洗咖啡杯需要的时间, 喝完咖啡的时间 + 自然干净的时间);
            return Math.min(Math.max(washLine, drinks[index]) + a, drinks[index] + b);
        }

        // 第1种情况: 当前咖啡杯选择清洗
        // wash 是我当前的咖啡杯，洗完的时间
        int wash = Math.max(washLine, drinks[index]) + a;
        // 洗完剩下所有的咖啡杯最早的结束时间
        int next1 = process(drinks, a, b, index + 1, wash);

        // 当前杯子选择在咖啡杯中洗的情况下最快的结束时间 = Math.max(当前杯子洗完的时间, 剩下杯子洗完的时间);
        int p1 = Math.max(wash, next1);

        // 第二种情况: 当前咖啡杯选择自然干净

        // 当前杯子挥发干净的时间
        int dry = drinks[index] + b;
        // 洗完剩下所有的咖啡杯最早的结束时间
        int next2 = process(drinks, a, b, index + 1, washLine);

        // 当前杯子选择挥发干净的情况下最快的结束时间 = Math.max(当前杯子挥发干净的时间, 剩下杯子洗完的时间);
        int p2 = Math.max(dry, next2);

        // 返回两种选择更快的那种选择
        return Math.min(p1, p2);
    }

    public static int minTime3(int[] arr, int n, int a, int b) {
        return 0;
    }
}
